/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/06
 */
package CodingTest.AC20190406;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。

 说明: 叶子节点是指没有子节点的节点。

 示例:

 输入:

    1
 /   \
 2     3
 \
 5

 输出: ["1->2->5", "1->3"]

 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 */
public class binaryTreePaths {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){val = x;}
    }
    //方法一：
    public List<String> binaryTreePaths1(TreeNode root){
       List<String> ret = new ArrayList<>();
       StringBuffer sb = new StringBuffer();
       helper(root,ret,sb);
       return ret;
    }
    public void helper(TreeNode node,List<String> list,StringBuffer sb){
        if(node == null) return ;
        if(node.left == null && node.right == null){
            list.add(sb.append(node.val).toString());
        }
        else if(node.left != null&&node.right ==null){
            helper(node.left,list,sb.append(node.val+"->"));
        }else if(node.left == null && node.right != null){
            helper(node.right,list,sb.append(node.val+"->"));
        }else{
            StringBuffer sb2 = new StringBuffer(sb);
            helper(node.left,list,sb.append(node.val+"->"));
            helper(node.right,list,sb2.append(node.val+"->"));
        }

    }}
    ///////////////////////////////////////////////////////////////
    //方法二：

